package protect.week05;

import java.util.Stack;

/**
 * @author thinkpad - 83start
 * @version v1.0
 * @create 2022/10/1 10:37
 * @package protect.week05
 * @description 20. 有效的括号
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 * <p>
 * 有效字符串需满足：
 * <p>
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 每个右括号都有一个对应的相同类型的左括号。
 *  
 * <p>
 * 示例 1
 * <p>
 * 输入：s = "()"
 * 输出：true
 * 示例 2：
 * <p>
 * 输入：s = "()[]{}"
 * 输出：true
 * 示例 3：
 * <p>
 * 输入：s = "(]"
 * 输出：false
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/valid-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Ch01_IsValid {
    public boolean isValid(String s) {

        int i = 0;
        char e, x;
        SqStackClass<Character> st = new SqStackClass<>();
        while (i < s.length()) {
            e = s.charAt(i);
            // 所有的左括号进栈
            if (e == '(' || e == '{' || e == '[') {
                st.push(e);
            } else {
                if (e == ')') {
                    if (st.empty()) {
                        return false;
                    }
                    if (st.peek() != '(') {
                        return false;
                    }
                    st.pop();
                }

                if (e == ']') {
                    if (st.empty()) {
                        return false;
                    }
                    if (st.peek() != '[') {
                        return false;
                    }
                    st.pop();
                }

                if (e == '}') {
                    if (st.empty()) {
                        return false;
                    }
                    if (st.peek() != '{') {
                        return false;
                    }
                    st.pop();
                }
            }
            i++;
        }

        // 判断栈是否为空
        return st.empty();
    }

    public boolean isValid2(String s) {

        int i = 0;
        char e, x;
        Stack<Character> st = new Stack<>();
        while (i < s.length()) {
            e = s.charAt(i);
            // 所有的左括号进栈
            if (e == '(' || e == '{' || e == '[') {
                st.push(e);
            } else {
                if (e == ')') {
                    if (st.empty()) {
                        return false;
                    }
                    if (st.peek() != '(') {
                        return false;
                    }
                    st.pop();
                }

                if (e == ']') {
                    if (st.empty()) {
                        return false;
                    }
                    if (st.peek() != '[') {
                        return false;
                    }
                    st.pop();
                }

                if (e == '}') {
                    if (st.empty()) {
                        return false;
                    }
                    if (st.peek() != '{') {
                        return false;
                    }
                    st.pop();
                }
            }
            i++;
        }

        // 判断栈是否为空
        return st.empty();
    }
}

class SqStackClass<E> {
    final int INITCAPACITY = 10;
    private int capacity;
    private E[] data;
    private int top;

    public SqStackClass() {
        data = (E[]) new Object[INITCAPACITY];
        capacity = INITCAPACITY;
        top = -1;
    }

    private void updateCapacity(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];

        for (int i = 0; i < top; i++) {
            newData[i] = data[i];
            capacity = newCapacity;
            data = newData;
        }
    }

    // ========================== 栈的基本操作 ==========================
    public boolean empty() {
        return top == -1;
    }

    /**
     * 进栈操作
     *
     * @param e
     */
    public void push(E e) {
        if (top == capacity - 1) {
            updateCapacity(2 * (top + 1));
        }
        // 进栈操作
        top++;
        data[top] = e;
    }

    /**
     * 出栈操作
     *
     * @return
     */
    public E pop() {
        if (empty()) {
            throw new IllegalArgumentException("出栈：栈空");
        }
        E e = (E) data[top];
        top--;
        if (capacity > INITCAPACITY && (top + 1) == (capacity / 4)) {
            updateCapacity(capacity / 2);
        }
        return e;
    }

    /**
     * 取栈顶元素
     *
     * @return
     */
    public E peek() {
        if (empty()) {
            throw new IllegalArgumentException("取栈顶元素：栈空");
        }
        return (E) data[top];
    }
}